package example2;

import common.TreeNode;
import utils.TreeNodeUtil;

//124. 二叉树中的最大路径和
public class LeetCode124 {
    public static void main(String[] args) {
        Integer[] arr = {5,4,8,11,null,13,4,7,2,null,null,null,1};
        TreeNode root = TreeNodeUtil.transferArrToTreeByDiGuiLonely(arr);
        System.out.println(new Solution124().maxPathSum(root));
    }
}

/**
 * 方法一： 自己想的方法：      记录经过每个节点的最大路径和，然后遍历找出最大的
 *
 * 每个节点的最大路径和要么等于左边的手臂加自己、要么等于右边的手臂加自己、要么就是自己，
 * 要么就是两边的手臂加自己，比较这四个的最大值，最大的就是经过当前节点的最大路径和，
 * 将当前节点的val修改为这个最大值，用于后续遍历使用。然后构建函数中，这个节点的这一次进行返回，
 * 返回“左边的手臂加自己”、“右边的手臂加自己”、“自己”这三个中的最大值，因为路径中一个节点只能出现一次，
 * 也就是路径中走的时候只能向前，不能向后，也就不能有岔路，所以不能返回“两边的手臂加自己”，
 * 然后它的父节点拿到它返回的其中一个的最大值，就是父节点的左手臂或右手臂。
 *
 * 优化：可以通过一个成员变量max记录最大值，每次构建节点最大值的时候可以顺便记录当前已遍历的所有节点的路径和的最大值，
 * 构建完成后直接返回max，可以少一遍遍历
 */
class Solution124 {
    private int max;

    public int maxPathSum(TreeNode root) {
        //递归遍历树，为每个节点计算经过此节点的最大路径和
        buildNodeMax(root);
        //然后遍历树的每个节点，得到最大的路径和
        return getMax(root);
    }

    //递归遍历二叉树的每个节点，为每个节点计算经过当前节点的最大路径和，并返回经过根节点的最大路径和
    public int buildNodeMax(TreeNode root){
        if(root == null)    return 0;
        int leftMax = buildNodeMax(root.left);
        int rightMax = buildNodeMax(root.right);
        int l = leftMax + root.val;
        int r = rightMax + root.val;
        int m = leftMax + rightMax + root.val;
        int now = root.val;
        root.val = Math.max(m,Math.max(root.val,Math.max(l,r)));
        return Math.max(now,Math.max(l,r));
    }

    //遍历二叉树，获取最大的一个节点值
    public int getMax(TreeNode root){
        if(root == null)    return 0;
        int max = root.val;
        if(root.left != null){
            int l = getMax(root.left);
            if(max < l) max = l;
        }
        if(root.right != null){
            int r = getMax(root.right);
            if(max < r) max = r;
        }
        return max;
    }
}
